class Cache {
    countLimit = 0;
    map = {};
    // 记录已经设置过的key
    keys = [];
    constructor(options) {
        const { countLimit } = options;
        this.countLimit = countLimit;
    }

    set = (key, value) => {
        // 表示当前没有存过该key
        if (!this.map[key]) {
            this.valid();
            // 插入，每次换了新的值
            this.keys.unshift({
                key: key,
                count: 0,
            });
        }
        this.map[key] = value;
    }

    get = (key) => {
        // 每次访问需要做一个排序
        this.sort(key);
        return this.map[key];
    }

    valid = () => {
        const curentKeyLength = this.keys.length;
        // 超过数量了
        if (curentKeyLength > this.countLimit) {
            // 访问次数最少的出队列
            const { key } = this.keys.shift();
            // 删除保存的值
            delete this.map[key];
        }
    }

    // 一次遍历，每次找到访问次数最小的，排到队顶就行
    sort = (key) => {
        let flag = false;
        // 如果是队顶的那个元素被访问，才需要重新找到最小的
        if (key !== this.keys[0].key) {
            flag = true;
        }
        const curentKeyLength = this.keys.length;
        let minIndex = 0;
        // 保证一定能找到最小的就行
        let min = this.keys[0].count + 2;
        for (let i = 0; i < curentKeyLength; i ++) {
            const item = this.keys[i];
            // 遍历到当前访问的key，让count++
            if (item.key === key) {
                item.count++;
            }
            if (!flag) {
                // 做比较
                if (item.count < min) {
                    min = item.count;
                    minIndex = i;
                }
            }
        }
        // 做替换
        const temp = this.keys[minIndex];
        this.keys[minIndex] = this.keys[0];
        this.keys[0] = temp;
    }
}